One class of problem involving multiple-adversarial agents (such as security problems) can be formulated as a defender-attacker game in which a first intelligent agent (also referred to here as the “defender”) will use limited defensive resources to protect against an attack by a second intelligent adversary (also referred to here as the “attacker”) that uses limited offensive resources.
The game theoretic features of such a game are that the attacker gets to observe the defender's mixed strategy over a period of observation before committing to an attack. The attacker chooses a means of attack without knowing the defender's strategy for the day of the attack. The rewards are not zero-sum or symmetric. For example, a convoy protection problem can be formulated as a defender-attacker game in which the defender varies its choice of possible routes and the attacker chooses an ambush site based on its observations of the routes chosen by the defender.
Such defender-attacker games are often modeled as Stackelberg games. The Decomposed Optimal Bayesian Stackelberg Solver (DOBSS) is described in Paruchuri, P., J. Pearce, and S. Kraus, “Playing Games for Security: An Efficient Exact Algorithm for Solving Bayesian Stackelberg Games”, Proc. of 7tha Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2008), ed. by Berger, Burg, and Nishiyama, May 12-16, Estoril, Portugal, 2008, which is referred to here as the “Paruchuri Article” and which is hereby incorporated herein by reference. In the DOBSS approach, a mixed-integer linear program (MILP) is formulated for a defender-attacker game for which the various attacks and defenses can be enumerated. The MILP problem is solved to find optimal mixed strategies for the defender-attacker game.
For example, Table 1 shows a normal form Stackelberg game for a simple leader-follower problem in which the leader comprises a defender and the follower comprises an attacker.
TABLE 1Simple Normal Form GameCDA2, 14, 0B1, 03, 2
Where:                iεI Defender's strategy        jεJ Attacker's strategy        Rij Reward to defender under defense i and attack j        cij Reward to attacker under defense i and attack j        xiε[0,1] Fraction of occasions that defender will choose i        qjε0,1 qj=1 if chosen attack is j, else qj=0        
In this example, the defender chooses a “mixed” defender strategy. As used herein, a “strategy” refers to a set of “actions” taken by a particular agent. For example, a mixed leader strategy refers to a set of actions taken by the leader, where the various leader actions need not all be the same. More formally, the mixed strategy is expressed as 0≦xi≦1.
The defender tries to maximize its strategy, knowing that the attacker will choose its best attack against whatever mixed defense the defender picks. This can be formularized in Equation (1).
                                          max            x                    ⁢                                    ∑              i                        ⁢                                          ∑                j                            ⁢                                                R                  ij                                ⁢                                  x                  i                                ⁢                                  q                  j                                                                    ⁢                                  ⁢                              s            .            t            .                                                  ⁢            q                    =                                    argmax              q                        ⁢                                          ∑                i                            ⁢                                                ∑                  j                                ⁢                                                      c                    ij                                    ⁢                                      x                    i                                    ⁢                                      q                    j                                                                                      ⁢                                  ⁢                                            ∑              i                        ⁢                          x              i                                =          1                ⁢                                  ⁢                                            ∑              j                        ⁢                          q              j                                =          1                ⁢                                  ⁢                  ∀                                    i              ⁢                                                          ⁢              0                        ≤                          x              i                        ≤            1                          ⁢                                  ⁢                  ∀                                    j              ⁢                                                          ⁢                              q                j                                      ∈                          {                              0                ,                1                            }                                                          (        1        )            
Using the approach described in the Paruchuri Article, it is possible to convert Equation (1) into a Mixed Integer Quadratic Program (MIQP) as shown in Equation (2) by taking advantage of standard optimality conditions for the inner optimization problem.
                                          max                          x              ,              q              ,              a                                ⁢                                    ∑              i                        ⁢                                          ∑                j                            ⁢                                                R                  ij                                ⁢                                  x                  i                                ⁢                                  q                  j                                                                    ⁢                                  ⁢                  s          .          t          .                                          ⁢                      ∀                                          j                ⁢                                                                  ⁢                0                            ≤                              (                                  a                  -                                                            ∑                      i                                        ⁢                                                                  c                        ij                                            ⁢                                              x                        i                                                                                            )                            ≤                                                (                                      1                    -                    q                                    )                                ⁢                M                                                    ⁢                                  ⁢                                            ∑              i                        ⁢                          x              i                                =                                    1              ⁢                                                          ⁢                                                ∑                  j                                ⁢                                  q                  j                                                      =            1                          ⁢                                  ⁢                  ∀                                    i              ⁢                                                          ⁢              0                        ≤                          x              i                        ≤            1                          ⁢                                  ⁢                  ∀                                    j              ⁢                                                          ⁢                              q                j                                      ∈                          {                              0                ,                1                            }                                      ⁢                                  ⁢                  0          ≤          a          ≤          M                                    (        2        )            
where M is a large constant such that:
                    M        >>                              max            j                    ⁢                                    ∑              i                        ⁢                          c              ij                                                          (        3        )            
A dual objective a of the inner problem can be defined for Equation (2), which means that for a solution x,q,a we will have a=maxj Σi cijxi.
Using the approach described in the Paruchuri Article, the problem defined in Table 1 can be expressed using Equation (2) to get the system of equations as follows (where M=3 to satisfy Equation (3)).
                                                        max                                                x                  1                                ,                                  x                  2                                ,                                  q                  1                                ,                                  q                  2                                ,                a                                      ⁢                                                  ⁢                          2              ⁢                              x                1                            ⁢                              q                1                                              +                      4            ⁢                                                  ⁢                          x              1                        ⁢                          q              2                                +                                    x              2                        ⁢                          q              1                                +                      3            ⁢                          x              2                        ⁢                          q              2                                      ⁢                                  ⁢                              s            .            t            .                                                  ⁢            0                    ≤                      a            -                          x              1                                ≤                      3            ⁢                          (                              1                -                                  q                  1                                            )                                      ⁢                                  ⁢                  0          ≤                      a            -                          2              ⁢                                                          ⁢                              x                2                                              ≤                      3            ⁢                          (                              1                -                                  q                  2                                            )                                      ⁢                                  ⁢                                            x              1                        +                          x              2                                =          1                ⁢                                  ⁢                                            q              1                        +                          q              2                                =          1                ⁢                                  ⁢                              0            ≤                          x              1                                ,                                    x              2                        ≤            1                          ⁢                                  ⁢                              q            1                    ,                                    q              2                        ∈                          {                              0                ,                1                            }                                      ⁢                                  ⁢                  0          ≤          a          ≤          3                                    (        4        )            
The optimal solution to Equation (4) is x1=2/3; x2=1/3; q1=0; q2=1; a=2/3. The strategy results in a payoff to the attacker of 2/3 and a payoff to the defender of 11/3.
The next stage in the approach described in the Paruchuri Article is to linearize the MIQP of Equation (2). This is done by defining the variables {zij} where:
                              z          ij                =                              x            i                    ⁢                      q            j                                              (        5        )                                          x          i                =                              ∑            j                    ⁢                      z            ij                                              (        6        )            
The resulting Mixed Integer Linear Program is as follows:
                                          max                          z              ,              q              ,              a                                ⁢                                          ⁢                                    ∑              i                        ⁢                                          ∑                j                            ⁢                                                R                  ij                                ⁢                                  z                  ij                                                                    ⁢                                  ⁢                  s          .          t          .                                          ⁢                      ∀                                          j                ⁢                                                                  ⁢                0                            ≤                              (                                  a                  -                                                            ∑                      i                                        ⁢                                                                  c                        ij                                            (                                                                        ∑                          h                                                ⁢                                                  z                          ih                                                                    )                                                                      )                            ≤                                                (                                      1                    -                                          q                      j                                                        )                                ⁢                M                                                    ⁢                                  ⁢                                            ∑              i                        ⁢                                          ∑                j                            ⁢                              z                ij                                              =          1                ⁢                                  ⁢                                            ∑              j                        ⁢                          q              j                                =          1                ⁢                                  ⁢                  ∀                                    i              ⁢                                                ∑                  j                                ⁢                                  z                  ij                                                      ≤            1                          ⁢                                  ⁢                  ∀                                    jq              j                        ≤                                          ∑                i                            ⁢                              z                ij                                      ≤            1                          ⁢                                  ⁢                  ∀                                    ij              ⁢                                                          ⁢              0                        ≤                          z              ij                        ≤            1                          ⁢                                  ⁢                  ∀                                    jq              j                        ∈                          {                              0                ,                1                            }                                      ⁢                                  ⁢                  0          ≤          a          ≤          M                                    (        7        )            
where M is a large constant satisfying Equation (3).
The problem defined in Table 1 can be expressed using Equation (7) to get the following system of equations (where M=3 to satisfy Equation (3)).
                                                        max                                                z                  11                                ,                                  z                  12                                ,                                  z                  21                                ,                                  z                  22                                ,                                  q                  1                                ,                                  q                  2                                ,                a                                      ⁢                                                  ⁢                          2              ⁢                              z                11                                              +                      4            ⁢                          z              12                                +                      z            21                    +                      3            ⁢                                                  ⁢                          z              22                                      ⁢                                  ⁢                              s            .            t            .                                                  ⁢            0                    ≤                      a            -                          z              11                        -                          z              12                                ≤                      3            ⁢                          (                              1                -                                  q                  1                                            )                                      ⁢                                  ⁢                  0          ≤                      a            -                          2              ⁢                              z                21                                      -                          2              ⁢                              z                22                                              ≤                      3            ⁢                          (                              1                -                                  q                  2                                            )                                      ⁢                                  ⁢                                            z              11                        +                          z              12                        +                          z              21                        +                          z              22                                =          1                ⁢                                  ⁢                                            q              1                        +                          q              2                                =          1                ⁢                                  ⁢                                            z              11                        +                          z              12                                ≤          1                ⁢                                  ⁢                                            z              21                        +                          z              22                                ≤          1                ⁢                                  ⁢                              q            1                    ≤                                    z              11                        +                          z              12                                ≤          1                ⁢                                  ⁢                              q            2                    ≤                                    z              12                        +                          z              22                                ≤          1                ⁢                                  ⁢                              0            ≤                          z              11                                ,                      z            12                    ,                      z            21                    ,                                    z              22                        ≤            1                          ⁢                                  ⁢                              q            1                    ,                                    q              2                        ∈                          {                              0                ,                1                            }                                      ⁢                                  ⁢                  0          ≤          a          ≤          3                                    (        8        )            
The optimal solution to this system of Equations (8) is z11=z21=0, z12=2/3, z22=1/3, q1=0, q2=1, a=2/3. The strategy results in a payoff to the attacker of 2/3 and a payoff to the defender of 11/3.
However, solving the MILP problem that results from the DOBSS approach described in the Paruchuri Article can be cumbersome and computationally intensive for real-word applications.